package suanfa.dp;

import java.util.Arrays;

public class begtest {
    /**
     * 动态规划算法之背包问题
     */
        public static void main(String[] args) {
            //w即重量数组，存放所有待放物品的重量
            int[] w={1,4,3};
            //val即价值数组，存放对应w数组物品的价值
            int[] val={1500,3000,2000};
            //m即背包允许存放的物品的最大重量
            int m=4;
            //n代表数组的长度，也是物品的数量
            int n=val.length;
            //表示我们填的表： v[i][j]在前i个物品中能够装入容量为j的背包的物品的最大价值
            int[][] v=new int[n+1][m+1];
            //为了记录放入商品的情况，方便一会儿输出，我们定义这个二维数组
            int[][] path=new int[n+1][m+1];

            //初始化第一行和第一列，这里在本程序中，我们可以不去处理，因为默认都是0
            for(int i=0;i<v.length;i++){
                v[i][0]=0;
            }
            for(int j=0;j<v[0].length;j++){
                v[0][j]=0;
            }
            // int[] w={1,4,3};
            //int[] val={1500,3000,1000};
        /*
        0磅       1磅       2磅         3磅        4磅
   0     0         0         0          0          0
 苹果    0         1500      1500      1500         1500
 小米    0         1500      1500      1500         3000
 华为    0         1500      1500      2000         3500
         */
            //动态规划的处理过程
            for(int i=1;i<v.length;i++){   //循环3次   三行
                for(int j=1;j<v[0].length;j++){
                    //公式
                    //当准备加入的新增商品容量大于当前背包的容量时，就直接使用上一个单元格的装入策略
                    if(w[i-1]>j){
                        v[i][j]=v[i-1][j];
                    }else{
                        //当准备加入的新增商品容量小于等于当前背包的容量时，装入的公式：
                    /*
                    j>w[i-1]:  v[i][j]=max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]])

                    v[i-1][j]:就是上一个单元格装入的最大值
                    v[i]:表示当前商品的价值
                    v[i-1][j-w[i-1]]:装入i-1商品到剩余空间的j-w[i]的最大值
                     */
                        if(v[i-1][j]<val[i-1]+v[i-1][j-w[i-1]]){
                            System.out.println("i:"+i+",j:"+j);
                            System.out.println("val[i-1]:"+val[i-1]+","+"v[i-1]:"+ Arrays.toString(v[i - 1]) +",v[i-1][j-w[i-1]]:"+v[i-1][j-w[i-1]]);
                            // i=3  j=4
                            //v[3][4]=3000+v[2][4-3]
                            v[i][j]=val[i-1]+v[i-1][j-w[i-1]];
                            System.out.println("v[i][j]:"+v[i][j]);
                            path[i][j]=1;
                        }else{
                            v[i][j]=v[i-1][j];
                        }

                    }
                }
            }
            //输出一下v，看看目前的情况
            for(int i=0;i<v.length;i++){
                for(int j=0;j<v[i].length;j++){
                    System.out.print(v[i][j]+" ");
                }
                System.out.println();
            }
            //输出最后放入的哪些商品
            int i=path.length-1;
            int j=path[0].length-1;
            while(i>0&&j>0){
                if(path[i][j]==1){
                    System.out.printf("第%d个商品放入背包\n",i);
                    j-=w[i-1];  //容量 指向剩余容量
                }
                i--;
            }
        }
    }


